package com.shuang.backtracking3;

import java.util.ArrayList;
import java.util.List;

public class LetterCombinations {
    //设置全局变量存储最后的结果
    List<String> list = new ArrayList<>();

    public List<String> letterCombinations(String digits) {

        //特殊情况直接返回空的结果集合
        if (digits == null || digits.length() == 0) {
            return list;
        }

        //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
        String[] numString = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

        //回溯算法
        backTracking(digits, numString, 0);

        return list;
    }

    //每次迭代获取一个字符串，所以会涉及大量的字符串拼接，所以这里选择更为高效的 StringBuilder
    //temp 用于临时存放每次拼接好结果的字符串 保存到结果集中
    StringBuilder temp = new StringBuilder();

    //index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。
    private void backTracking(String digits, String[] numString, int index) {

        //终止条件
        if (index == digits.length()) {
            list.add(temp.toString());
            return;
        }

        //取出给的数字字符串中索引位置index的数字对应的字符串 str
        String str = numString[digits.charAt(index) - '0'];

        //处理 数字字符串中有0，1 或者 * #的情况
        if (str == null || str.length() == 0){
            return;
        }

        //for循环遍历
        for (int i = 0; i < str.length(); i++) {
            //拼接字符
            temp.append(str.charAt(i));

            //递归 处理下一层
            backTracking(digits, numString, index + 1);

            //回溯
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}
